package alo.p19;

/**
 * @ClassName FindMaxSumMatrix
 * @Description 最大和子矩阵
 * @Author Fanxc
 * @DATE 2021/3/15 16:56
 * @Version 1.0
 */
public class FindMaxSumMatrix {
    int findMaxSumMatrix(int[][] A,int n){
        int[][] M=new int[n][n];
        //计算列的垂直前缀之和
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j==0){
                    M[j][i]=A[j][i];
                }else {
                    M[j][i]=A[j][i]+M[j-1][i];
                }
            }
        }
        int maxSoFar=0;
        int min,subMatrix;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                min=0;
                subMatrix=0;
                for (int k = 0; k < n; k++) {
                    if (i==0){
                        subMatrix+=M[j][k];
                    }else {
                        subMatrix+=M[j][k]-M[i-1][k];
                    }
//                    if (subMatrix<min){
//                        min=subMatrix;
//                    }
//                    if ((subMatrix-min)>maxSoFar){
//                        maxSoFar=subMatrix-min;
//                    }
                    if (subMatrix>maxSoFar){
                        maxSoFar=subMatrix;
                    }
                }

            }
        }
        return maxSoFar;
    }
}
